//==========================================================================
// Copyright (c) 2000-2008,  Elastos, Inc.  All Rights Reserved.
//==========================================================================

#include <mantle.h>

DLinkNode GlobalAS::s_freeList;

#ifdef DEBUG_KMUTEX
KMutex GlobalAS::s_listLock(__FILE__, __LINE__);
#else
KMutex GlobalAS::s_listLock;
#endif //DEBUG_KMUTEX

UInt32 GlobalAS::AllocP(UInt32 cPages)
{
    SpaceBlock * pBlock;
    UInt32 uBase = 0;

    assert(cPages != 0);

    s_listLock.Lock();

    // Find the free block reversely
    //
    ForEachDLinkNodeReversely(SpaceBlock *, pBlock, &s_freeList) {
        if (pBlock->m_cPages == cPages) {
            // Detach free block that match cPages want to allocate
            //
            pBlock->Detach();
            uBase = pBlock->m_uBase;
            delete pBlock;
            goto ExitAlloc;
        }
        else if (pBlock->m_cPages > cPages) {
            // Split a free block for allocation
            //
            pBlock->m_cPages -= cPages;
            uBase = pBlock->m_uBase + P_TO_B(pBlock->m_cPages);
            goto ExitAlloc;
        }
    }

ExitAlloc:
    s_listLock.Unlock();
    return uBase;
}

UInt32 GlobalAS::AllocFixedP(UInt32 uBase, UInt32 cPages)
{
    SpaceBlock * pBlock;
    UInt32 uRetBase = 0;

    assert(!PAGE_OFFSET(uBase));
    assert(cPages != 0);

    s_listLock.Lock();

    // Find the free block reversely
    //
    ForEachDLinkNode(SpaceBlock *, pBlock, &s_freeList) {
        if (FALL_INTO(uBase, pBlock->m_uBase, P_TO_B(pBlock->m_cPages))
            && FALL_INTO(uBase + P_TO_B(cPages) - 1, pBlock->m_uBase, P_TO_B(pBlock->m_cPages))) {
            if (pBlock->m_cPages == cPages) {
                // Detach free block that match cPages want to allocate
                //
                pBlock->Detach();
                uRetBase = pBlock->m_uBase;
                delete pBlock;
                goto ExitAlloc;
            }
            else {
                assert(pBlock->m_cPages > cPages);

                // Split a free block for allocation
                //
                if (pBlock->m_uBase == uBase) {
                    pBlock->m_cPages -= cPages;
                    uRetBase = pBlock->m_uBase;
                    pBlock->m_uBase = uBase + P_TO_B(cPages);
                }
                else if (B_TO_P(uBase - pBlock->m_uBase) == pBlock->m_cPages - cPages) {
                    pBlock->m_cPages -= cPages;
                    uRetBase = pBlock->m_uBase + P_TO_B(pBlock->m_cPages);
                }
                else {
                    SpaceBlock * pNewBlock;
                    UInt32 uNewBase, cNewPages;

                    cNewPages = pBlock->m_cPages - cPages - B_TO_P(uBase - pBlock->m_uBase);
                    uNewBase  = uBase + P_TO_B(cPages);

                    pNewBlock = new SpaceBlock(uNewBase, cNewPages);
                    if (pNewBlock) {
                        pBlock->m_cPages -= (cPages + cNewPages);
                        pBlock->InsertNext(pNewBlock);
                        uRetBase = uBase;
                    }
                }

                goto ExitAlloc;
            }
        }
    }

ExitAlloc:
    s_listLock.Unlock();
    assert(uRetBase == 0 || uRetBase == uBase);
    return uRetBase;
}

void GlobalAS::FreeP(UInt32 uBase, UInt32 cPages)
{
    SpaceBlock * pNext, * pPrev, *pBlock;

    s_listLock.Lock();

    ForEachDLinkNodeReversely(SpaceBlock *, pPrev, &s_freeList) {
        if (uBase > pPrev->m_uBase) {
            assert(uBase >= pPrev->m_uBase + PagesToBytes(pPrev->m_cPages));

            pNext = (SpaceBlock *)pPrev->m_pNext;

            if (pPrev->m_uBase + P_TO_B(pPrev->m_cPages) == uBase) {
                // Merge into prev block
                //
                pPrev->m_cPages += cPages;
                if (uBase + P_TO_B(cPages) == pNext->m_uBase) {
                    // And merge into next block
                    //
                    pNext->Detach();
                    pPrev->m_cPages += pNext->m_cPages;
                    delete pNext;
                }
                s_listLock.Unlock();
                return;
            }
            else if (uBase + P_TO_B(cPages) == pNext->m_uBase) {
                // Merge into next block
                //
                pNext->m_uBase = uBase;
                pNext->m_cPages += cPages;
                s_listLock.Unlock();
                return;
            }
            else {
                goto NewFreeNode;
            }
        }
        assert(uBase != pPrev->m_uBase);
    }

NewFreeNode:
    pBlock = new SpaceBlock(uBase, cPages);
    if (pBlock) {
        pPrev->InsertNext(pBlock);
    }
    s_listLock.Unlock();
}

#ifndef _RELEASE

void GlobalAS::View()
{
    SpaceBlock *pBlock;
    UInt32 uNextBase = COMMON_BASE;

    kprintf("---- GlobalAS VIEW ----\n");
    kprintf("  BASE          SIZE    STAT\n");

    s_listLock.Lock();
    ForEachDLinkNode(SpaceBlock *, pBlock, &s_freeList) {
        if (uNextBase != pBlock->m_uBase) {
            kprintf("%08x    %08x, Used\n",
                uNextBase, pBlock->m_uBase - uNextBase);
        }
        kprintf("%08x    %08x, Free\n",
                pBlock->m_uBase, P_TO_B(pBlock->m_cPages));
        uNextBase = pBlock->m_uBase + P_TO_B(pBlock->m_cPages);
    }
    s_listLock.Unlock();

    if (uNextBase != COMMON_LIMIT) {
        kprintf("%08x    %08x, Used\n",
            uNextBase, COMMON_LIMIT - uNextBase);
    }
    kprintf("\n");
}

#endif // _RELEASE
